package lib

//link to 45
func init() {
	Probs = append(Probs, Problem{
		Num:         55,
		Discription: "跳跃游戏",
		Level:       2,
		Labels: map[string]int{
			"贪心":   1,
			"双指针滑动": 1,
		},
	})
}

func CanJump(nums []int) bool {
	if len(nums) <= 1 {
		return true
	}

	preStart := 0
	preEnd := 0
	for {
		tempEnd := preEnd
		for i := preStart; i <= preEnd; i++ {
			tempEnd = max(tempEnd, nums[i]+i)
		}

		if tempEnd == preEnd {
			return false
		}
		if tempEnd >= len(nums)-1 {
			return true
		}

		preStart = preEnd + 1
		preEnd = tempEnd
	}
}
